DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2022.8

Slimming down Petri Boxes: Compact Petri Net Models of Control Flows

Authors: Victor Khomenko, Maciej Koutny, and Alex Yakovlev

Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)

Abstract

We look at the construction of compact Petri net models corresponding to process algebra expressions supporting sequential, choice, and parallel compositions. If "silent" transitions are disallowed, a construction based on Cartesian product is traditionally used to construct places in the target Petri net, resulting in an exponential explosion in the net size. We demonstrate that this exponential explosion can be avoided, by developing a link between this construction problem and the problem of finding an edge clique cover of a graph that is guaranteed to be complement-reducible (i.e., a cograph). It turns out that the exponential number of places created by the Cartesian product construction can be reduced down to polynomial (quadratic) even in the worst case, and to logarithmic in the best (non-degraded) case. As these results affect the "core" modelling techniques based on Petri nets, eliminating a source of an exponential explosion, we hope they will have applications in Petri net modelling and translations of various formalisms to Petri nets.

Cite as

Victor Khomenko, Maciej Koutny, and Alex Yakovlev. Slimming down Petri Boxes: Compact Petri Net Models of Control Flows. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{khomenko_et_al:LIPIcs.CONCUR.2022.8,
  author =	{Khomenko, Victor and Koutny, Maciej and Yakovlev, Alex},
  title =	{{Slimming down Petri Boxes: Compact Petri Net Models of Control Flows}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.8},
  URN =		{urn:nbn:de:0030-drops-170710},
  doi =		{10.4230/LIPIcs.CONCUR.2022.8},
  annote =	{Keywords: Petri net, Petri box, cograph, edge clique cover, control flow, static construction, local construction, interface graph, Burst automata, composition}
}

Search Results

Documents authored by Koutny, Maciej

Slimming down Petri Boxes: Compact Petri Net Models of Control Flows

Abstract

Cite as

Thanks for your feedback!

Could not send message